#include <bits/stdc++.h>
//#include <cstdint> // c++11
/*#if __cplusplus < 201103L
#error This file requires compiler and library support for the \
ISO C++ 2011 standard. This support is currently experimental, and must be \
enabled with the -std=c++11 or -std=gnu++11 compiler options.
#endif
*/
using namespace std;

#define int64_t signed long long
#define uint64_t unsigned long long

struct adjacList_t
{
   int a;
   int top, size;
   int *to, *ne, *fi; // fi: last
   int *de, *si, *parents;
   bool hasRoot;
#define ANC_SIZE_I 1024 * 2
#define ANC_SIZE_J 32
   int anc[ANC_SIZE_I][ANC_SIZE_J], lg2maxN;
   adjacList_t()
   {
      top = 0;
      init();
   }
   adjacList_t(int len, bool hasRoot) : size(len), hasRoot(hasRoot)
   {
      top = 0;
      if (hasRoot)
      {
         fi = new int[len]();
         ne = new int[len]();
         to = new int[len]();
      }
      else
      {
         fi = new int[len]();
         ne = new int[len * 2]();
         to = new int[len * 2]();
      }
      de = new int[len]();
      si = new int[len]();
      parents = new int[len]();
      lg2maxN = log2(size);
      if (lg2maxN != log2(size))
         lg2maxN++;

      //lg2maxN = ANC_SIZE_J;
      init();
   }

   void init()
   {
      memset(anc, 0, sizeof(anc));
   }

   ~adjacList_t()
   {
      if (fi)
         delete fi;
      if (ne)
         delete ne;
      if (to)
         delete to;
   }

   void link(int frX, int toY)
   {
      hasRoot ? linkHasRoot(frX, toY) : linkNoRoot(frX, toY);
   }

   void linkHasRoot(int frX, int toY)
   {
      to[++top] = toY, ne[top] = fi[frX], fi[frX] = top;
   }

   void linkNoRoot(int frX, int toY)
   {
      to[++top] = toY, ne[top] = fi[frX], fi[frX] = top;
      to[++top] = frX, ne[top] = fi[toY], fi[toY] = top;
   }

   void print()
   {
      printf("%3s%5s%5s%5s\n", "i", "to[]", "ne[]", "fi[]");
      for (int i = 0; i < 22; i++)
      {
         printf("%3d%5d%5d%5d\n", i, to[i], ne[i], fi[i]);
      }
   }

   void dfs(int x)
   {
      printf("%d.", x);
      for (int i = fi[x]; i; i = ne[i])
         dfs(to[i]);
      printf("\n");
   }

   void dfs(int x, int fath)
   {
      printf(" %d,", x);
      for (int i = fi[x]; i; i = ne[i])
         if (to[i] != fath)
            dfs(to[i], x);
      printf("\n");
   }

   void getsi(int x, int fath)
   {
      parents[x] = fath;
      de[x] = de[fath] + 1;
      si[x] = 1;
      anc[x][0] = fath;
      for (int i = 1; i <= lg2maxN; i++)
         anc[x][i] = anc[anc[x][i - 1]][i - 1];
      for (int i = fi[x]; i; i = ne[i])
         if (to[i] != fath)
            getsi(to[i], x), si[x] += si[to[i]];
   }

   void printDeSi()
   {
      printf("%3s%5s%5s%5s%5s\n", "i", "fa", "to[]", "dep", "si");
      for (int i = 0; i < 22; i++)
      {
         printf("%3d%5d%5d%5d%5d\n", i, parents[i], to[i], de[i], si[i]);
      }
   }

   int LCA_a1(int x, int y)
   {
      while (x != y)
      {
         if (de[x] > de[y])
            x = parents[x];
         else
            y = parents[y];
      }
      return x;
   }

   // MoT 树上倍增 Multiplication of trees
   int LCA_MoT(int x, int y)
   {
      if (de[x] < de[y])
         swap(x, y);
      int delta = de[x] - de[y];
      for (int j = 0; j < ANC_SIZE_J; j++)
         if ((1 << j) & delta)
            x = anc[x][j];

      if (x == y)
         return x;
      for (int j = lg2maxN; j >= 0; j--)
         if (anc[x][j] != anc[y][j])
            x = anc[x][j], y = anc[y][j];

      return anc[x][0];
   }

   int diameter(int *p1, int *p2)
   {
      int x = 1, y = 1;
      getsi(1, 0);
      for (int i = 2; i < size; i++)
         if (de[i] > de[x])
            x = i;
      for (int i = 2; i < size; i++)
         de[i] = 0;
      getsi(x, 0);
      y = 1;
      for (int i = 2; i < size; i++)
         if (de[i] > de[y])
            y = i;
      *p1 = x;
      *p2 = y;
      return de[y];
   }
};

int main()
{
   adjacList_t t1(100, true);
   adjacList_t t2(100, false);
   int x, y, n = 0;
   while (cin >> x >> y)
   {
      t1.link(x, y);
      t2.link(x, y);
   }
   t1.print();
   t2.print();
   t1.dfs(0);
   t2.dfs(1, 0);
   t2.getsi(1, 0);
   t2.printDeSi();

   x = 3, y = 5;
   printf(" LCA(%d, %d) = %d\n", x, y, t2.LCA_a1(x, y));
   printf(" LCA(%d, %d) = %d @mot\n", x, y, t2.LCA_MoT(x, y));
   printf(" d(%d, %d) = %d\n", x, y, t2.diameter(&x, &y));
   x = 3, y = 5;
   printf(" LCA(%d, %d) = %d\n", x, y, t2.LCA_a1(x, y));
   printf(" LCA(%d, %d) = %d @mot\n", x, y, t2.LCA_MoT(x, y));

   return 0;
}

/*
      1
      |
      |
   11  2    3  9
   /        \
  /          \
4 5  10    6 7 8



0 1
0 2
0 3
1 4
1 5
3 6
3 7
3 8
0 9
1 10


3 6
3 7
0 1
0 2
3 8
0 3
1 4
1 5
0 9
1 10



1 0
2 0
3 0
4 1
5 1
6 3
7 3
8 3
9 0
10 1

6 3
7 3
1 0
2 0
8 3
3 0
4 1
5 1
9 0
10 1


NO ROOT:
11 1
1 2
1 3
11 4
11 5
3 6
3 7
3 8
9 1
11 10

*/
